package util

// TreeNode 二叉树结点
type TreeNode struct {
	Value       byte
	Left, Right *TreeNode
}

// ResetBytesByBinTree 借助二叉树重置字节数组
// 按照完全二叉树新建二叉树，然后中序遍历二叉树，将遍历结果存入新的数组
func ResetBytesByBinTree(raw []byte) []byte {
	root := BuildBinTree(raw)
	return InorderBinTree(root)
}

// BuildBinTree 建立完全二叉树
func BuildBinTree(raw []byte) *TreeNode {
	if len(raw) == 0 {
		return nil
	}
	root := &TreeNode{Value: raw[0]}
	q := []*TreeNode{root}
	index, rawLen := 1, len(raw)
	for len(q) > 0 {
		node := q[0]
		if index < rawLen {
			leftNode := &TreeNode{Value: raw[index]}
			index++
			node.Left = leftNode
			if node.Left != nil {
				q = append(q, node.Left)
			}
		}
		if index < rawLen {
			rightNode := &TreeNode{Value: raw[index]}
			index++
			node.Right = rightNode
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		q = q[1:]
	}
	return root
}

// InorderBinTree 中序遍历二叉树，将结果存入字节数组
func InorderBinTree(root *TreeNode) []byte {
	var r []byte
	if root == nil {
		return r
	}
	var st []*TreeNode
	p := root
	for p != nil || len(st) > 0 {
		for p != nil {
			st = append(st, p)
			p = p.Left
		}
		node := st[len(st)-1]
		st = st[0 : len(st)-1]
		r = append(r, node.Value)
		p = node.Right
	}
	return r
}
